// 377. 组合总和 Ⅳ(排列问题)
// 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 
// 中找出并返回总和为 target 的元素组合的个数。

// 题目数据保证答案符合 32 位整数范围。
// 输入：nums = [1,2,3], target = 4
// 输出：7
// 解释：
// 所有可能的组合为：
// (1, 1, 1, 1)
// (1, 1, 2)
// (1, 2, 1)
// (1, 3)
// (2, 1, 1)
// (2, 2)
// (3, 1)
// 请注意，顺序不同的序列被视作不同的组合。
// 思路：排列问题，先遍历背包，再遍历物品
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
 var combinationSum4 = function(nums, target) {
    let dp=new Array(target+1).fill(0);
    dp[0]=1;
    for(let i=0;i<=target;i++){
        for(let j=0;j<nums.length;j++){
            if(i>=nums[j])// 只有背包大于物品的时候才可以装
                dp[i]+=dp[i-nums[j]];
        }
    }
    return dp[target];
};